package problems.contest;

import utils.beans.TreeNode;

import java.util.*;

/**
 * 第 102 场双周赛
 * <p>https://leetcode.cn/contest/biweekly-contest-102</p>
 *
 * @author dubulingbo, 2023-04-15 22:16.
 */
public class BCT102 {
    /**
     * T1.
     */
    public int[] findColumnWidth(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[] ans = new int[n];

        for (int i = 0; i < n; ++i) {
            int max = 0;
            for (int j = 0; j < m; ++j) {
                int abs = Math.abs(grid[j][i]);
                int l = len(abs);
                l = grid[j][i] < 0 ? l + 1 : l;
                max = Math.max(l, max);
            }
            ans[i] = max;
        }

        return ans;
    }

    private int len(int k) {
        if (k == 0) return 1;
        int ret = 0;
        while (k > 0) {
            ++ret;
            k /= 10;
        }
        return ret;
    }

    /**
     * T2.
     */
    public long[] findPrefixScore(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];

        long max = 0;

        for (int i = 0; i < n; ++i) {
            max = Math.max(nums[i], max);
            ans[i] = max + nums[i];
            if (i > 0) {
                ans[i] += ans[i - 1];
            }
        }

        return ans;
    }


    /**
     * T3.
     */
    public TreeNode replaceValueInTree_1(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode[]> que = new ArrayDeque<>();
        root.val = 0;

        if (root.left != null) {
            que.offer(new TreeNode[]{root, root.left});
        }

        if (root.right != null) {
            que.offer(new TreeNode[]{root, root.right});
        }


        while (!que.isEmpty()) {
            Map<TreeNode, Integer> sumMap = new HashMap<>();
            int sum = 0;
            for (int i = que.size(); i > 0; --i) {
                TreeNode[] cur = que.poll();
                sumMap.put(cur[0], sumMap.getOrDefault(cur[0], 0) + cur[1].val);
                sum += cur[1].val;
                if (cur[1].left != null) {
                    que.offer(new TreeNode[]{cur[1], cur[1].left});
                }

                if (cur[1].right != null) {
                    que.offer(new TreeNode[]{cur[1], cur[1].right});
                }

            }

            for (Map.Entry<TreeNode, Integer> e : sumMap.entrySet()) {
                TreeNode node = e.getKey();
                int value = e.getValue();
                int v = sum - value;
                if (node.left != null) {
                    node.left.val = v;
                }

                if (node.right != null) {
                    node.right.val = v;
                }
            }
        }

        return root;
    }

    public TreeNode replaceValueInTree(TreeNode root) {
        // 在 parent 层，处理 children 层
        if (root == null) return null;
        Queue<TreeNode> que = new ArrayDeque<>();
        // 根节点直接赋值 0
        root.val = 0;

        que.offer(root);

        while (!que.isEmpty()) {
            Map<TreeNode, Integer> sumMap = new HashMap<>();
            // 记录所有父节点的所有子节点值的和
            int sum = 0;
            for (TreeNode p : que) {
                sum += p.left != null ? p.left.val : 0;
                sum += p.right != null ? p.right.val : 0;
            }

            // 更新父节点的子节点的值
            for (int i = que.size(); i > 0; --i) {
                TreeNode cur = que.poll();

                int cs = cur.left != null ? cur.left.val : 0;
                cs += cur.right != null ? cur.right.val : 0;

                if (cur.left != null) {
                    cur.left.val = sum - cs;
                    que.offer(cur.left);
                }

                if (cur.right != null) {
                    cur.right.val = sum - cs;
                    que.offer(cur.right);
                }
            }
        }

        return root;
    }

    /**
     * T4|6336. 设计可以求最短路径的图类
     * <p>https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/</p>
     */
    class Graph {
        // 边的权值：es[i][j] 表示 i -> j，有一条权值 es[i][j] 的有向边
        // es[i][j]=Integer.MAX_VALUE 表示 i -> j 为不可达
        int[][] es;
        // 节点总数
        int nodeCnt;

        public Graph(int n, int[][] edges) {
            es = new int[n][n];
            this.nodeCnt = n;

            // 初始化所有点相互之间的距离
            for (int i = 0; i < n; ++i) {
                Arrays.fill(es[i], Integer.MAX_VALUE);
            }

            for (int[] e : edges) {
                es[e[0]][e[1]] = e[2];
            }
        }

        public void addEdge(int[] edge) {
            es[edge[0]][edge[1]] = edge[2];
        }

        public int shortestPath(int node1, int node2) {
            if (node1 == node2) return 0;

            int[] dis = new int[nodeCnt];
            boolean[] vis = new boolean[nodeCnt];

            // 加入集合
            vis[node1] = true;

            // 更新 node1 -> 其他节点的直接距离
            for (int i = 0; i < nodeCnt; ++i) {
                dis[i] = es[node1][i];
            }

            // 最多松弛 nodeCnt - 1 次
            for (int i = 1; i < nodeCnt; ++i) {
                // 到下一个最短路径的点
                int nxt = -1;
                // 到下一个点的最短距离
                int minDis = Integer.MAX_VALUE;

                for (int j = 0; j < nodeCnt; ++j) {
                    if (!vis[j] && dis[j] < minDis) {
                        nxt = j;
                        minDis = dis[j];
                    }
                }

                // 没有多余的到可达点，直接退出
                // 优化：已经到达终点
                if (nxt == -1 || nxt == node2) break;

                // 找到一个点
                vis[nxt] = true;

                // 松弛操作，通过 nxt 节点
                for (int j = 0; j < nodeCnt; j++) {
                    if (!vis[j] // 未加入集合
                            && es[nxt][j] != Integer.MAX_VALUE // 可达
                            && minDis + es[nxt][j] < dis[j]) { // 可松弛，更新最小值
                        dis[j] = minDis + es[nxt][j];
                    }
                }
            }

            return dis[node2] == Integer.MAX_VALUE ? -1 : dis[node2];
        }
    }
}
